package com.mj.listen2._01_排序;

import com.mj.listen2._01_排序.cmp.Sort;

/**
 * 计数排序优化实现
 */
public class _09_CountingSort2 extends Sort<Integer> {
    @Override
    protected void sort() {
        // 找出最大值、最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }

        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];

        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            // array[i] - min 表示原始数组中i索引位置的元素K，对应counts中的索引是 k-min，即：array[i] - min
            counts[array[i] - min]++;
        }

        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            // 当前位置的次数为当前次数与前面所有次数相加之和。
            counts[i] += counts[i - 1];
        }

        // 开辟一个全新的数组，用于存储排好序的元素
        int[] newArray = new int[array.length];
        // 对原始数组从后往前遍历，这样能保证稳定性
        for (int i = array.length - 1; i >= 0; i--) {
            // counts[array[i] - min] - 1  表示元素 array[i] 在有序数组中的索引。
            newArray[--counts[array[i] - min]] = array[i];
        }

        // 将排好序的数组元素还原给原来的数组
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
